#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
class Solution
{
public:
    // 合法字符的位置要先找到
    vector<int> findSubstring(string s, vector<string> &words)
    {
        vector<int> ans;
        int len = words[0].size(), n = s.size();
        unordered_map<string, int> hash1;
        unordered_map<string, int> hash2;
        // 统计一共有多少个字符，并统计
        for (auto &e : words)
            hash1[e]++;

        // all_size是所有有效字符的个数
        int all_size = words.size();

        for (int i = 0; i < len; ++i)
        {
            int left = i, right = i;
            hash2.clear();
            int sz = 0, valid_size = 0;
            for (; right < n;)
            {
                // 如果剩下的字符数足够一个给定子串长度，那就继续判断
                // 如果不满足，那也就没必要继续判断了
                string tmp;
                if (n - right >= len)
                    tmp = s.substr(right, len);
                else
                    break;
                right += len;
                // if(right == 10) cout << tmp << ' ' << valid_size <<  endl;
                // 放进集合中去

                hash2[tmp]++;
                sz++;
                // 放进去之后，需要看一下是否是合理的
                // cout << tmp << ' ' << hash2["cb"] << endl;
                // if(left == 6) cout << tmp << endl;
                if (hash1.find(tmp) != hash1.end() && hash2[tmp] <= hash1[tmp])
                    valid_size++;
                // cout << valid_size << endl;
                if (sz > all_size)
                {
                    // 需要把最前面的去掉
                    // 如果在删去前就是多余的，那么删去不需要变化
                    // 如果是多余的，那么删去之后就需要让有效字符个数减少
                    string tt = s.substr(left, len);
                    // cout << "tt:" << tt << endl;
                    // cout << hash1[tt] << ' ' << hash2[tt] << endl;
                    // if(left == 4) cout << hash2["bc"] <<  endl;
                    if (hash1.find(tt) != hash1.end() && hash2[tt] <= hash1[tt])
                        --valid_size;
                    // cout << valid_size << endl;
                    hash2[tt]--;
                    if (hash2[tt] == 0)
                        hash2.erase(tt);
                    // cout << "erase:" << tmp << endl;
                    left += len;
                    // cout << left << ' ' << right << endl;
                }
                if (valid_size == all_size)
                    ans.push_back(left);
            }
        }
        return ans;
    }
};